package search;

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
        int values[] = {8, 17, 26, 32, 40, 72, 87, 99};
        System.out.println("二分法查找，排序数组： " + Arrays.toString(values));

        System.out.print("二分法查找 39，");
        System.out.println(binarySearch_recursive(values, 39));
        System.out.print("二分法查找 87，");
        System.out.println(binarySearch_recursive(values, 87));

        System.out.print("非递归二分法查找 39，");
        System.out.println(binarySearch_recursive(values, 39));
        System.out.print("非递归二分法查找 87，");
        System.out.println(binarySearch_non_recursive(values, 87));
    }

    //在升序排序数组value中，二分法查找关键字为key元素，若查找成功返回下标，否则返回-1。递归算法
    public static int binarySearch_recursive(int[] value, int key) {
        return binarySearch_recursive(value, key, 0, value.length - 1);
    }

    //在升序排序数组value的begin～end范围内，二分法查找关键字为key元素。递归算法
    public static int binarySearch_recursive(int[] value, int key, int begin, int end) {
        if (begin <= end) {
            int mid = (begin + end) / 2;                             //中间位置，当前比较元素位置
            System.out.print("[" + mid + "]=" + value[mid] + "？");   //显示比较中间结果，可省略
            if (value[mid] == key) {
                return mid;                                           //查找成功，返回元素下标
            }
            if (key < value[mid]) {                                   //尚未成功，进行二分查找
                return binarySearch_recursive(value, key, begin, mid - 1);
            } else {
                return binarySearch_recursive(value, key, mid + 1, end);
            }
        }
        return -1;
    }


    //在升序排序数组value中，二分法查找关键字为key元素，若查找成功返回下标，否则返回-1。非递归算法
    public static int binarySearch_non_recursive(int[] value, int key) {
        return binarySearch_non_recursive(value, key, 0, value.length - 1);
    }

    //在升序排序数组value的begin～end范围内，二分法查找关键字为key元素。非递归算法
    public static int binarySearch_non_recursive(int[] value, int key, int begin, int end) {
        while (begin <= end) {
            int mid = (begin + end) / 2;                       //取中间位置，当前比较元素位置
            System.out.print("[" + mid + "]=" + value[mid] + "？"); //显示比较中间结果，可省略
            if (key == value[mid])                         //相等
                return mid;                                //查找成功
            if (key < value[mid])                          //key对象较小
                end = mid - 1;                               //查找范围缩小到前半段
            else begin = mid + 1;                            //查找范围缩小到后半段
        }
        return -1;                                         //查找不成功
    }
}
